package _binary_tree

import common.v2.Node
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/*

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/
https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html#_116-%E5%A1%AB%E5%85%85%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84%E4%B8%8B%E4%B8%80%E4%B8%AA%E5%8F%B3%E4%BE%A7%E8%8A%82%E7%82%B9%E6%8C%87%E9%92%88
117. 填充每个节点的下一个右侧节点指针 II
同
116. 填充每个节点的下一个右侧节点指针


116. 填充每个节点的下一个右侧节点指针
给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。

示例 1：
输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]

示例 2:
输入：root = []
输出：[]
 */
class leetcode_116 {
    @Test
    fun test_1() {
        val root = Node(1)
        val n2 = Node(2)
        val n3 = Node(3)
        val n4 = Node(4)
        val n5 = Node(5)
        val n6 = Node(6)
        val n7 = Node(7)
        root.left = n2
        root.right = n3
        n2.left = n4
        n2.right = n5
        n3.left = n6
        n3.right = n7
        val actual: CharArray = print(connect(root))
        val expect: CharArray = charArrayOf('1', '#', '2', '3', '#', '4', '5', '6', '7', '#')
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }
    @Test
    fun test_2() {
        val actual: CharArray = print(connect(null))
        val expect: CharArray = charArrayOf()
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    fun print(root: Node?): CharArray {
        if (root == null) {
            return charArrayOf()
        }
        val list: ArrayList<Char> = ArrayList<Char>()
        val queue: LinkedList<Node> = LinkedList<Node>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            val size = queue.size
            for (i in 1..size) {
                val node = queue.poll()
                list.add(node.`val`.digitToChar())
                if (node.next == null) {
                    list.add('#')
                }
                node.left?.let {
                    queue.offer(it)
                    it.next = node.right
                }
                node.right?.let {
                    queue.offer(it)
                }
            }
        }
        return list.toCharArray()
    }

    fun connect(root: Node?): Node? {
        // 层序遍历，只不过在单层遍历的时候记录一下本层的头部节点，然后在遍历的时候让前一个节点指向本节点就可以了
        if (root == null) {
            return null
        }

        val queue: LinkedList<Node> = LinkedList<Node>()
        queue.offer(root)

        while(!queue.isEmpty()){
            var size: Int = queue.size
            var prev: Node? = null
            while(size-- > 0){
                val node = queue.poll()
                prev?.let{
                    it.next = node
                }
                prev = node

                node.left?.let{queue.offer(it)}

                node.right?.let{queue.offer(it)}
            }
        }
        return root
    }

}